{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Tree Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteTreeNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除树节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵以节点 0 为根节点的树，定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的总数为&nbsp;<code>nodes</code>&nbsp;个；</li>\n",
    "\t<li>第&nbsp;<code>i</code> 个节点的值为&nbsp;<code>value[i]</code>&nbsp;；</li>\n",
    "\t<li>第&nbsp;<code>i</code> 个节点的父节点是&nbsp;<code>parent[i]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你删除节点值之和为 0 的每一棵子树。</p>\n",
    "\n",
    "<p>在完成所有删除之后，返回树中剩余节点的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/30/1421_sample_1.png\" style=\"height: 347px; width: 403px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-2]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nodes = 5, parent = [-1,0,1,0,0], value = [-672,441,18,728,378]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nodes = 5, parent = [-1,0,0,1,1], value = [-686,-842,616,-739,-746]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nodes &lt;= 10^4</code></li>\n",
    "\t<li><code>parent.length == nodes</code></li>\n",
    "\t<li><code>0 &lt;= parent[i] &lt;= nodes - 1</code></li>\n",
    "\t<li><code>parent[0] == -1</code>&nbsp;表示节点 <code>0</code> 是树的根。</li>\n",
    "\t<li><code>value.length == nodes</code></li>\n",
    "\t<li><code>-10^5 &lt;= value[i] &lt;= 10^5</code></li>\n",
    "\t<li>题目输入数据 <strong>保证</strong> 是一棵 <strong>有效的树</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-tree-nodes](https://leetcode.cn/problems/delete-tree-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-tree-nodes](https://leetcode.cn/problems/delete-tree-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[-1,0,0,1,2,2,2]\\n[1,-2,4,0,-2,-1,-1]', '7\\n[-1,0,0,1,2,2,2]\\n[1,-2,4,0,-2,-1,-2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        outdegree = [0] * nodes\n",
    "        visited = [0] * nodes\n",
    "        child = [[] for _ in range(nodes)]\n",
    "        for i in range(nodes):\n",
    "            if parent[i] != -1: \n",
    "              outdegree[parent[i]] += 1\n",
    "              child[parent[i]].append(i)\n",
    "            else:\n",
    "              root = [i]\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nodes):\n",
    "            if outdegree[i] == 0:    stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "          temp = []\n",
    "          for cur in stack:\n",
    "            if parent[cur] != -1:\n",
    "              value[parent[cur]] += value[cur]\n",
    "              visited[parent[cur]] += 1\n",
    "              if visited[parent[cur]] == outdegree[parent[cur]]:\n",
    "                temp.append(parent[cur])\n",
    "                outdegree[parent[cur]] += sum(outdegree[i] for i in child[parent[cur]])\n",
    "          stack = temp\n",
    "\n",
    "        while root:\n",
    "          temp = []\n",
    "          for cur in root:\n",
    "            if value[cur] == 0:\n",
    "              nodes -= outdegree[cur] + 1\n",
    "            else:\n",
    "              temp.extend(child[cur])\n",
    "          root = temp\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        outdegree = [0] * nodes\n",
    "        visited = [0] * nodes\n",
    "        child = [[] for _ in range(nodes)]\n",
    "        for i in range(nodes):\n",
    "            if parent[i] != -1: \n",
    "              outdegree[parent[i]] += 1\n",
    "              child[parent[i]].append(i)\n",
    "            else:\n",
    "              root = [i]\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nodes):\n",
    "            if outdegree[i] == 0:    stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "          temp = []\n",
    "          for cur in stack:\n",
    "            if parent[cur] != -1:\n",
    "              value[parent[cur]] += value[cur]\n",
    "              visited[parent[cur]] += 1\n",
    "              if visited[parent[cur]] == outdegree[parent[cur]]:\n",
    "                temp.append(parent[cur])\n",
    "                outdegree[parent[cur]] += sum(outdegree[i] for i in child[parent[cur]])\n",
    "          stack = temp\n",
    "\n",
    "        while root:\n",
    "          temp = []\n",
    "          for cur in root:\n",
    "            if value[cur] == 0:\n",
    "              nodes -= outdegree[cur] + 1\n",
    "            else:\n",
    "              temp.extend(child[cur])\n",
    "          root = temp\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        outdegree = [0] * nodes\n",
    "        visited = [0] * nodes\n",
    "        child = [[] for _ in range(nodes)]\n",
    "        for i in range(nodes):\n",
    "            if parent[i] != -1: \n",
    "              outdegree[parent[i]] += 1\n",
    "              child[parent[i]].append(i)\n",
    "            else:\n",
    "              root = [i]\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nodes):\n",
    "            if outdegree[i] == 0:    stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "          temp = []\n",
    "          for cur in stack:\n",
    "            if parent[cur] != -1:\n",
    "              value[parent[cur]] += value[cur]\n",
    "              visited[parent[cur]] += 1\n",
    "              if visited[parent[cur]] == outdegree[parent[cur]]:\n",
    "                temp.append(parent[cur])\n",
    "                outdegree[parent[cur]] += sum(outdegree[i] for i in child[parent[cur]])\n",
    "          stack = temp\n",
    "\n",
    "        while root:\n",
    "          temp = []\n",
    "          for cur in root:\n",
    "            if value[cur] == 0:\n",
    "              nodes -= outdegree[cur] + 1\n",
    "            else:\n",
    "              temp.extend(child[cur])\n",
    "          root = temp\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        outdegree = [0] * nodes\n",
    "        visited = [0] * nodes\n",
    "        child = [[] for _ in range(nodes)]\n",
    "        for i in range(nodes):\n",
    "            if parent[i] != -1: \n",
    "              outdegree[parent[i]] += 1\n",
    "              child[parent[i]].append(i)\n",
    "            else:\n",
    "              root = [i]\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nodes):\n",
    "            if outdegree[i] == 0:    stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "          temp = []\n",
    "          for cur in stack:\n",
    "            if parent[cur] != -1:\n",
    "              value[parent[cur]] += value[cur]\n",
    "              visited[parent[cur]] += 1\n",
    "              if visited[parent[cur]] == outdegree[parent[cur]]:\n",
    "                temp.append(parent[cur])\n",
    "                outdegree[parent[cur]] += sum(outdegree[i] for i in child[parent[cur]])\n",
    "          stack = temp\n",
    "\n",
    "        while root:\n",
    "          temp = []\n",
    "          for cur in root:\n",
    "            if value[cur] == 0:\n",
    "              nodes -= outdegree[cur] + 1\n",
    "            else:\n",
    "              temp.extend(child[cur])\n",
    "          root = temp\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        child_num_dict = {}\n",
    "        child_dict = {}\n",
    "        value_sum = {}\n",
    "        for i, v in enumerate(value):\n",
    "            value_sum[i] = v\n",
    "        for i, each in enumerate(parent):\n",
    "            if each == -1:\n",
    "                continue\n",
    "            child_num_dict[each] = child_num_dict.get(each, 0) + 1\n",
    "            if each not in child_dict:\n",
    "                child_dict[each] = []\n",
    "            child_dict[each].append(i)\n",
    "        leaf_queue = []\n",
    "        for i in range(nodes):\n",
    "            if i not in child_num_dict:\n",
    "                leaf_queue.append(i)\n",
    "        while len(leaf_queue):\n",
    "            c = leaf_queue[0]\n",
    "            leaf_queue.pop(0)\n",
    "            c_parent = parent[c]\n",
    "            if c_parent == -1:\n",
    "                continue\n",
    "            child_num_dict[c_parent] -= 1\n",
    "            value_sum[c_parent] += value_sum[c]\n",
    "\n",
    "            if child_num_dict[c_parent] == 0:\n",
    "                leaf_queue.append(c_parent)\n",
    "            \n",
    "        result = 0\n",
    "        current_list = [0]\n",
    "        while len(current_list):\n",
    "            parent = current_list.pop(0)\n",
    "            if value_sum[parent] == 0:\n",
    "                continue\n",
    "            result += 1\n",
    "            current_list += child_dict.get(parent, [])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        n = nodes\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if parent[i] != -1:\n",
    "                graph[parent[i]].append(i)\n",
    "        \n",
    "        def helper(u):\n",
    "            nonlocal n\n",
    "            \n",
    "            total, sz = value[u], 1\n",
    "            for v in graph[u]:\n",
    "                a, b = helper(v)\n",
    "                total += a\n",
    "                sz += b\n",
    "            \n",
    "            if not total:\n",
    "                n -= sz\n",
    "                return 0, 0\n",
    "            return total, sz\n",
    "        \n",
    "        helper(0)\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for i,p in enumerate(parent):\n",
    "            g[p].append(i)\n",
    "        def dfs(k):\n",
    "            v,a=value[k],1\n",
    "            for nk in g[k]:\n",
    "                nv,na=dfs(nk)\n",
    "                v+=nv\n",
    "                a+=na\n",
    "            if v==0:return v,0\n",
    "            return v,a\n",
    "        _,res=dfs(0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        g = [[] for i in range(nodes)]\n",
    "\n",
    "        for i in range(1, nodes):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        def dfs(x):\n",
    "            res, num = value[x], 1\n",
    "            for y in g[x]:\n",
    "                if y == -1: continue\n",
    "                i, j = dfs(y)\n",
    "                res += i\n",
    "                num += j\n",
    "            if res == 0:\n",
    "                nonlocal nodes\n",
    "                nodes -= num\n",
    "                return 0, 0\n",
    "            return res, num\n",
    "        dfs(0)\n",
    "        return nodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "\n",
    "        n = nodes\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parent):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            graph[p].append(i)\n",
    "\n",
    "        \n",
    "        res = n\n",
    "        def dfs(i: int) -> tuple:\n",
    "            nonlocal res\n",
    "            val, size = value[i], 1 #分别返回子树的值sum 和 节点个数\n",
    "            for j in graph[i]:\n",
    "                v, s = dfs(j)\n",
    "                val, size = val + v, size + s\n",
    "            if val == 0:\n",
    "                res -= size\n",
    "                size = 0\n",
    "            # res -= size if val == 0 else 0\n",
    "            return val, size\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "\n",
    "        def dfs(x):\n",
    "            res = [1, value[x]]\n",
    "            for y in edges[x]:\n",
    "                nex = dfs(y)\n",
    "                res[0] += nex[0]\n",
    "                res[1] += nex[1]\n",
    "            if not res[1]:\n",
    "                return [0, 0]\n",
    "            return res\n",
    "\n",
    "        edges = [[] for _ in range(nodes)]\n",
    "        for i in range(1, nodes):\n",
    "            edges[parent[i]].append(i)\n",
    "        return dfs(0)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, n: int, parent: List[int], value: List[int]) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dct[parent[i]].append(i)\n",
    "        \n",
    "        \n",
    "        def dfs(x):\n",
    "            res = [value[x], 1]\n",
    "            for y in dct[x]:\n",
    "                nex = dfs(y)\n",
    "                res[0] += nex[0]\n",
    "                res[1] += nex[1]\n",
    "            if res[0] == 0:\n",
    "                return [0, 0]\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return dfs(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        g=[[] for _ in range(nodes)]\n",
    "        root=0\n",
    "        for i in range(nodes):\n",
    "            if parent[i]!=-1:\n",
    "                g[parent[i]].append(i)\n",
    "            else:\n",
    "                root=i\n",
    "        def dfs(cur):\n",
    "            if g[cur]==None:\n",
    "                return [value[cur],1]\n",
    "            res=[0,0]\n",
    "            for i in g[cur]:\n",
    "                temp=dfs(i)\n",
    "                res[0]+=temp[0]\n",
    "                res[1]+=temp[1]\n",
    "            if res[0]+value[cur]==0:\n",
    "                return [0,0]\n",
    "            return [res[0]+value[cur],res[1]+1]\n",
    "        return dfs(root)[1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        # 预处理父节点：子节点\n",
    "        g = [[] for _ in range(nodes)]\n",
    "        for son,fa in enumerate(parent):\n",
    "            if fa!= -1:\n",
    "                g[fa].append(son)\n",
    "        del_remain = [1]*nodes\n",
    "        def dfs(x):\n",
    "            for y in g[x]:\n",
    "                dfs(y)\n",
    "                del_remain[x] += del_remain[y]\n",
    "                value[x] += value[y]\n",
    "            if value[x] == 0:\n",
    "                del_remain[x] = 0\n",
    "        dfs(0)\n",
    "        return del_remain[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        edges = {x: list() for x in range(nodes)}\n",
    "        for x, p in enumerate(parent):\n",
    "            if p != -1:\n",
    "                edges[p].append(x)\n",
    "                \n",
    "        def dfs(u):\n",
    "            node_cnt = 1\n",
    "            for v in edges[u]:\n",
    "                node_num = dfs(v)\n",
    "                value[u] += value[v]\n",
    "                node_cnt += node_num\n",
    "            if value[u] == 0:\n",
    "                node_cnt = 0\n",
    "            return node_cnt\n",
    "\n",
    "        res = dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        edges = {x: list() for x in range(nodes)}\n",
    "        for x, p in enumerate(parent):\n",
    "            if p != -1:\n",
    "                edges[p].append(x)\n",
    "        \n",
    "        node_cnt = [1] * nodes\n",
    "        \n",
    "        def dfs(u):\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "                value[u] += value[v]\n",
    "                node_cnt[u] += node_cnt[v]\n",
    "            if value[u] == 0:\n",
    "                node_cnt[u] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return node_cnt[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        for i in range(nodes):\n",
    "            if parent[i] != -1:\n",
    "                edges[parent[i]].append(i)\n",
    "        \n",
    "        node_cnt = [1] * nodes\n",
    "        \n",
    "        def dfs(node):\n",
    "            for v in edges[node]:\n",
    "                dfs(v)\n",
    "                value[node] += value[v]\n",
    "                node_cnt[node] += node_cnt[v]\n",
    "            if value[node] == 0:\n",
    "                node_cnt[node] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return node_cnt[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        g = [[] for _ in range(nodes)]\n",
    "        # 预处理\n",
    "        for son,fa in enumerate(parent):\n",
    "            if fa!= -1:\n",
    "                g[fa].append(son)\n",
    "        # x:y x是y的父亲\n",
    "        remain = [1]*nodes\n",
    "        def dfs(x):\n",
    "            for y in g[x]:\n",
    "                dfs(y)\n",
    "                value[x] += value[y]\n",
    "                remain[x] += remain[y]\n",
    "            if value[x] == 0:\n",
    "                remain[x] = 0\n",
    "        dfs(0)\n",
    "        return remain[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        # 遇到二叉树的题目首先想到的是什么？\n",
    "        # 问题分解\n",
    "        # 复杂问题：整颗二叉树让你删除节点值之和的每一颗子树\n",
    "        # 子问题：删除左二叉树节点值之和的每一颗子树，删除右二叉树节点值之和的每一棵子树，然后判断剩余的左二叉树，右二叉树和根节点是否是节点值之和为0\n",
    "        # 如果为0,返回0(表示剩余节点数目为0)，如果不为0，就返回根节点\n",
    "        # def dfs(root):\n",
    "        #     if ''：\n",
    "        #         return 0\n",
    "        #     left_remain = dfs(root.left)\n",
    "        #     right_remain = dfs(root.right)\n",
    "        #     if '左子树剩余节点+右子树剩余节点+root.val==0':\n",
    "        #         return 0\n",
    "        #     return left_remain + right_remain + 1\n",
    "\n",
    "        # return dfs(parent[0])\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        edges = {x: [] for x in range(nodes)}\n",
    "        for x, p in enumerate(parent):\n",
    "            if p != -1:\n",
    "                edges[p].append(x)\n",
    "        \n",
    "        node_cnt = [1] * nodes\n",
    "        \n",
    "        def dfs(u):\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "                value[u] += value[v]\n",
    "                node_cnt[u] += node_cnt[v]\n",
    "            if value[u] == 0:\n",
    "                node_cnt[u] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return node_cnt[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "        edges={i:list() for i in range(nodes)}\n",
    "        for i in range(nodes):\n",
    "            if parent[i]!=-1:\n",
    "                edges[parent[i]].append(i)\n",
    "        node_cnt=[1]*nodes\n",
    "        def dfs(node):\n",
    "            for v in edges[node]:\n",
    "                dfs(v)\n",
    "                value[node]+=value[v]\n",
    "                node_cnt[node]+=node_cnt[v]\n",
    "            if value[node]==0:\n",
    "                node_cnt[node]=0\n",
    "        dfs(0)\n",
    "        return node_cnt[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:\n",
    "      edges = {x : list() for x in range(nodes)}\n",
    "      for x, p in enumerate(parent):\n",
    "        if p != -1:\n",
    "          edges[p].append(x)\n",
    "      node_cnt = [1] * nodes\n",
    "      def dfs(u):\n",
    "        for v in edges[u]:\n",
    "          dfs(v)\n",
    "          value[u] += value[v]\n",
    "          node_cnt[u] += node_cnt[v]\n",
    "        if value[u] == 0:\n",
    "          node_cnt[u] = 0\n",
    "      dfs(0)\n",
    "      return node_cnt[0]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
